---
sidebar_position: 1
---

# Сортировка выбором

:::info

Основано на статьях ["Сортировка выбором"](http://cppstudio.com/post/459/), ["Сортировка выбором"](https://ru.wikipedia.org/wiki/Сортировка_выбором), ["Selection Sort Algorithm"](https://www.geeksforgeeks.org/selection-sort/), ["Сортировка выбором минимумов (максимумов)"](https://habr.com/ru/post/484798/) и ["Общие сведения об алгоритмах сортировки"](https://www.evkova.org/kursovye-raboty/obschie-svedeniya-ob-algoritmah-sortirovki).

:::

Пожалуй, самый простой алгоритм сортировок – это **сортировка выбором** (англ. *selection sort*). Судя по названию сортировки, необходимо что-то выбирать (*максимальный* или *минимальный* элементы массива). Алгоритм сортировки выбором находит в исходном массиве *максимальный* или *минимальный* элементы, в зависимости от того как необходимо сортировать массив, *по возрастанию* или *по убыванию*. Если массив должен быть отсортирован *по возрастанию*, то из исходного массива необходимо выбирать *минимальные элементы*. Если же массив необходимо отсортировать *по убыванию*, то выбирать следует *максимальные элементы*.

На массиве из $n$ элементов имеет время выполнения в худшем, среднем и лучшем случае $O(n^2)$, предполагая что сравнения делаются за постоянное время.

## Алгоритм

Шаги алгоритма:

- находим номер минимального значения в текущем списке;
- производим обмен этого значения со значением первой неотсортированной позиции (обмен не нужен, если минимальный элемент уже находится на данной позиции);
- теперь сортируем хвост списка, исключив из рассмотрения уже отсортированные элементы.

## Пример работы

Для того, чтобы отсортировать массив в порядке возрастания, следует на каждой итерации найти элемент с наибольшим значением. С ним нужно поменять местами последний элемент. Следующий элемент с наибольшим значением становится уже на предпоследнее место. Так должно происходить, пока элементы, находящиеся на первых местах в массиве, не окажутся в надлежащем порядке.

![Пример работы сортировки выбором](images/selection-sort-example.png)
